package com.xypower.sort;

//快速排序
public class quickSortTest {
    //快排时间复杂度 o(N*logN)
    public static  void  quickSort(int[] arr){
        if (arr==null || arr.length<2){
            return;
        }
        quickSort(arr,0,arr.length-1);
    }

    public static void quickSort(int[] arr,int L,int R){
        if(L==R){
            return;
        }
        //优化
//        if (L>R-60){
//            在arr[L...R]插入排序，常数系极低
//            o(N²)小样本量的时候，跑得快
//                    return;
//        }
        if (L<R){
            swap(arr,L+(int)(Math.random()*(R-L+1)),R);
            int[] p = partition(arr,L,R);
            quickSort(arr,L,p[0]-1);//<区间
            quickSort(arr,p[1]+1,R);//>区间
        }
    }

    //以arr[r]做划分，<p   =p     >p
    //返回等于区域(左边界,右边界)，返回长度为2的数组
    public static int[] partition(int[] arr,int L,int R){
        int less =L-1;      //<区右边界
        int more = R;       //>区左边界
        while (L<more){
            if (arr[L]<arr[R]){ //当前数小于划分值
                swap(arr,++less,L++);
            }else if (arr[L]>arr[R]){//当前数大于划分值
                swap(arr,--more,L);
            }else{
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }

    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
